{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 线性查找"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def linear_search(arr, key): # arr:输入列表，key是待查找元素\n",
    "    \"\"\"线性查找\"\"\"\n",
    "    for i, value in enumerate(arr):\n",
    "        if value == key:   # 如果找到元素，马上结束程序返回元素的下标\n",
    "            return i\n",
    "    return -1 # 如果没有找到，返回-1\n",
    "\n",
    "def linear_search_2(arr, key): # arr:输入列表，key是待查找元素\n",
    "    \"\"\"线性查找\"\"\"\n",
    "    for i, value in enumerate(arr):\n",
    "        if value == key:   # 如果找到元素，马上结束程序返回元素的下标\n",
    "            return i\n",
    "    else: # 可以增加else, 加强这个逻辑关系\n",
    "        return -1 # 如果没有找到，返回-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "arr = [10,30,40,20,50,70,90]\n",
    "print(linear_search(arr, 50))  # ４\n",
    "print(linear_search(arr, 77))  # -1\n",
    "print('---------------------')\n",
    "print(linear_search_2(arr, 50))  # ４\n",
    "print(linear_search_2(arr, 77))  # -1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 挑战：海底在哪里"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_deepest_point(arr):\n",
    "    max_index = 0    # 记录最大值下标\n",
    "    max_value = -1   # 记录最大值下标\n",
    "    for i, value in enumerate(arr):\n",
    "        # i是列表的下标，value是下标对应值\n",
    "        if max_value < value:  # 如果比最大值大，则记录下来\n",
    "            max_index = i\n",
    "            max_value = value\n",
    "    return max_index  # 返回结果下标\n",
    "\n",
    "def find_deepest_point_2(arr):\n",
    "    # 使用Python内置函数max()找最大值\n",
    "    # 列表内置函数index()找元素对应的下标\n",
    "    i = arr.index(max(arr))\n",
    "    return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(find_deepest_point([12,16,17,18,32,40,30,15,7,6,1]))\n",
    "print(find_deepest_point_2([12,16,17,18,32,40,30,15,7,6,1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint\n",
    "import time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "input_data = [randint(0, 5000) for _ in range(50000)]\n",
    "start = time.clock()  # 记录开始时间\n",
    "result = find_deepest_point(input_data)\n",
    "operation_time = time.clock() - start  # 运行时间\n",
    "print(\"方法１的结果：{}, 用时：{}\".format(result, operation_time))\n",
    "start = time.clock()  # 记录开始时间\n",
    "result = find_deepest_point_2(input_data)\n",
    "operation_time = time.clock() - start  # 运行时间\n",
    "print(\"方法2的结果：{}, 用时：{}\".format(result, operation_time))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 间隔查找\n",
    "### 二分查找"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 针对有序查找表的二分查找算法\n",
    "def binary_search(arr, key): # arr:输入列表，key是待查找元素\n",
    "    \"\"\"二分查找算法\"\"\"\n",
    "    first = 0         # 最小值的下标（左边界）\n",
    "    last = len(arr)-1 # 最大值的下标（右边界）\n",
    "    index = -1        # 记录目标值下标，若找不到返回-1\n",
    "    while (first <= last) and (index == -1):\n",
    "        # 循环退出条件1:找到目标元素，那么index就不等于-1\n",
    "        # 循环退出条件2:列表边界错误，说明序列中没有目标元素\n",
    "        mid = (first + last) // 2  # 计算序列中间元素下标\n",
    "        if arr[mid] == key:        # 若相等，则是找到目标元素\n",
    "            index = mid            # 记录目标元素下标\n",
    "        else:\n",
    "            if key < arr[mid]:     # 若小于中间元素，则看前半部分，修改右边界的值\n",
    "                last = mid - 1\n",
    "            else:\n",
    "                first = mid + 1    # 若大于中间元素，则看后半部分，修改左边界的值\n",
    "    return index\n",
    "\n",
    "# 递归方式\n",
    "def binary_search_recurse(arr, key, first, last):\n",
    "    \"\"\"二分查找算法 递归表现形式\"\"\"\n",
    "    if first <= last:              # 如果右边界不少于左边界，继续查找\n",
    "        mid = (first + last) // 2  # 计算序列中间元素下标\n",
    "        if arr[mid] == key:\n",
    "            return mid             # 返回结果：目标元素下标\n",
    "        elif key < arr[mid]:\n",
    "            # 若小于中间元素，则看前半部分，修改右边界的值\n",
    "            return binary_search_recurse(arr, key, first, mid-1)\n",
    "        else:\n",
    "            # 若大于中间元素，则看后半部分，修改左边界的值\n",
    "            return binary_search_recurse(arr, key, mid+1, last)\n",
    "    else:\n",
    "        # 边界异常，证明没有知道目标元素\n",
    "        return -1  # 若找不到返回-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "arr = [10,20,40,50,60,70,90]\n",
    "print(binary_search(arr, 70))\n",
    "print(binary_search_recurse(arr, 70, 0, len(arr)-1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 斐波那契查找"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "斐波那契查找算法\n",
    "时间复杂度O(log(n))\n",
    "找到元素返回元素值 \n",
    "否则返回-1\n",
    "\"\"\"\n",
    "def fibonacci_search(arr, key):\n",
    "    \"\"\"斐波那契查找算法\"\"\"\n",
    "    # 初始化斐波那契数列  \n",
    "    fib_N_2 = 0 # F(k-2)斐波那契数列值 \n",
    "    fib_N_1 = 1 # F(k-1)斐波那契数列值 \n",
    "    fib_next = fib_N_1 + fib_N_2 # 下一个斐波那契数列值，F(n)=f(n-1)+F(n-2)\n",
    "    length = len(arr) # 原始序列的长度\n",
    "    # 找到一个斐波那契数列值不小于序列的长度\n",
    "    while (fib_next < length): \n",
    "        fib_N_2 = fib_N_1 \n",
    "        fib_N_1 = fib_next \n",
    "        fib_next = fib_N_2 + fib_N_1\n",
    "    # 记录下标的偏移量\n",
    "    offset = -1 \n",
    "    # 当fib_next少于１，就是没有序列可以拆分，查找结束  \n",
    "    while (fib_next > 1):\n",
    "        # 找出中间元素的下标，但要确保下标不越界\n",
    "        i = min(offset + fib_N_2, length - 1) \n",
    "        # 如果中间元素比目标元素小，获取后半部分\n",
    "        if (arr[i] < key): \n",
    "            fib_next = fib_N_1 \n",
    "            fib_N_1 = fib_N_2 \n",
    "            fib_N_2 = fib_next - fib_N_1 \n",
    "            offset = i # 下标的偏移量为i\n",
    "        # 如果中间元素比目标元素大，获取前半部分，偏移量不变\n",
    "        elif (arr[i] > key): \n",
    "            fib_next = fib_N_1 \n",
    "            fib_N_1 = fib_N_2 \n",
    "            fib_N_2 = fib_next - fib_N_1 \n",
    "        else : \n",
    "            return i  # 刚好相等，返回元素下标\n",
    "    # 最后和最大元素值比较\n",
    "    if(fib_N_1 and offset < length -1) and (arr[offset+1] == key):\n",
    "        return offset+1 # 后面补充的元素都是最大元素，因此只需在偏移量+1，就是原始序列的下标\n",
    "    return -1  # 没有找到元素，返回-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "arr = [10,20,40,50,60,70,90]\n",
    "print(fibonacci_search(arr, 70))\n",
    "print(fibonacci_search(arr, 77))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 插值查找"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def interpolation_search(arr, key): # arr:输入列表，key是待查找元素\n",
    "    \"\"\"插值查找算法\"\"\"\n",
    "    low = 0         # 最小值的下标（左边界）\n",
    "    high = len(arr)-1 # 最大值的下标（右边界）\n",
    "    index = -1        # 记录目标值下标，若找不到返回-1\n",
    "    while (low < high) and (index == -1):\n",
    "        # 循环退出条件1:找到目标元素，那么index就不等于-1\n",
    "        # 循环退出条件2:列表边界错误，说明序列中没有目标元素\n",
    "        mid = low + int((high - low) * (key - arr[low])/(arr[high] - arr[low]))  # 计算序列中间元素下标\n",
    "        if arr[mid] == key:        # 若相等，则是找到目标元素\n",
    "            index = mid            # 记录目标元素下标\n",
    "        else:\n",
    "            if key < arr[mid]:     # 若小于中间元素，则看前半部分，修改右边界的值\n",
    "                high = mid - 1\n",
    "            else:\n",
    "                low = mid + 1    # 若大于中间元素，则看后半部分，修改左边界的值\n",
    "    return index # 没有找到目标元素，返回-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "arr = [10,20,40,50,60,70,90]\n",
    "print(interpolation_search(arr, 7))\n",
    "print(interpolation_search(arr, 40))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 跳转查找"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "def jump_search (arr, key):\n",
    "    \"\"\"跳转查找\"\"\"\n",
    "    length = len(arr)              # 序列长度\n",
    "    jump = int(math.sqrt(length))  # 计算跳跃的长度，也是子序列大小\n",
    "    left, right = 0, 0             # 初始化左右边界\n",
    "    while left < length and arr[left] <= key:  # 找到目标元素所在子序列\n",
    "        right = min(length - 1, left + jump - 1)   # 找到右边界下标\n",
    "        if arr[left] <= key and arr[right] >= key: # 目标元素是否在子序列中\n",
    "            break     # 如果是，跳出循环\n",
    "        left += jump; # 否则，跳到下一个子序列\n",
    "    # 结束循环后，判断是否找到子序列    \n",
    "    if left >= length or arr[left] > key:\n",
    "        # 如果左边界已经大于序列长度或者目标元素小于序列的最小值，说明没有找到目标元素，则返回-1\n",
    "        return -1\n",
    "    # 否则我们在子序列中用线性查找找出\n",
    "    right = min(length - 1, right) # 找到子序列的边界\n",
    "    for i, value in enumerate(arr[left:right+1]):\n",
    "        if value == key:   # 如果找到元素，马上结束程序返回元素的下标\n",
    "            return i + left # 因为i只是子序列的下标，所以要加上左边界的值才是原始序列的下标\n",
    "    return -1 # 若找不到返回-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "arr = [10,20,30,40,50,60,70,80,90]\n",
    "print(jump_search(arr, 40))\n",
    "print(jump_search(arr, 90))\n",
    "print(jump_search(arr, 41))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 挑战：晒水的最小半径"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_min_radius(points, water):\n",
    "    # 存放最长距离\n",
    "    max_lenght = 0\n",
    "    # 二分法前提是有序序列，我们使用内置函数排序\n",
    "    points.sort()\n",
    "    water.sort()\n",
    "    for p in points:\n",
    "        # 二分查找，在water中寻找与位置点p最近的晒水点\n",
    "        left = 0\n",
    "        right = len(water) - 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if water[mid] < p:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        # 情况1：若找到的值等于p ，则说明p处有一个晒水点，p到晒水点的最短距离为 0\n",
    "        if water[left] == p:\n",
    "            continue # 只是最小距离，可以忽略\n",
    "        # 情况2：若该晒水点的坐标值小于p ，说明该晒水点的坐标与p之间没有别的加热器\n",
    "        elif water[left] < p:\n",
    "            if max_lenght < p - water[left]:\n",
    "                max_lenght = p - water[left]\n",
    "        # 情况3：若该晒水点的坐标值大于p并且left不等于 0 ，说明p介于left和left-1之间，\n",
    "        elif left > 0:\n",
    "            # 该位置到晒水点的最短距离就是left和left-1处晒水点与p差值的最小值\n",
    "            tmp_res = min(water[left] - p, p - water[left - 1])\n",
    "            if max_lenght < tmp_res:\n",
    "                max_lenght = tmp_res\n",
    "        else: # 情况4:left=0, 所有晒水点都比p点大\n",
    "            if max_lenght < water[left] - p:\n",
    "                max_lenght = water[left] - p\n",
    "        print(max_lenght)\n",
    "    return max_lenght"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "points = [2,4,0,6,15,8,7,21]\n",
    "water = [20,0,1,2,19,17]\n",
    "print(findRadius(points, water))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 树表查找\n",
    "### 二叉树查找算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 引用tools.py上的类和函数,若不成功，请把对应函数复制过来这个文档，重新运行\n",
    "from tools import BinarySearchTreeNode as Tree, print_tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BinarySearchTree2(Tree):\n",
    "    def search(self, value):\n",
    "        \"\"\"二叉树查找\"\"\"\n",
    "        node = self\n",
    "        while node:\n",
    "            if value < node.value:   # 比结点值小，那么选择左子树\n",
    "                node = node.left\n",
    "            elif value > node.value: # 比结点值大，那么选择右子树\n",
    "                node = node.right\n",
    "            else:\n",
    "                return node          # 相等返回结点\n",
    "        self.insert(value)           # 如果没有找到元素则插入元素\n",
    "        return -1                    # 返回-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree  = BinarySearchTree2(20) # 创建根结点20，\n",
    "for data in [11,27,5,18,14,19]:  # 插入数值\n",
    "    tree.insert(data)\n",
    "print(\"-------原始二叉查找树-----------\")\n",
    "print_tree(tree)\n",
    "res = tree.in_order_traversal()\n",
    "print(\"中序遍历\",res)\n",
    "print(\"寻找元素１８\", tree.search(18))\n",
    "print(\"寻找元素29\", tree.search(29))\n",
    "print(\"-------当前二叉查找树-----------\")\n",
    "print_tree(tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree  = BinarySearchTree2(5) # 创建根结点20，\n",
    "for data in [11, 14, 18]:  # 插入数值\n",
    "    tree.insert(data)\n",
    "print_tree(tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " ### 2-3查找树"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "    \"\"\"创建2-3查找树结点类\"\"\"\n",
    "    def __init__(self, key):\n",
    "        self.key1 = key   # 至少一个值，那么最多是2个孩子结点\n",
    "        self.key2 = None  # 保存２个key，那么就有可能是3个孩子结点\n",
    "        self.left = None\n",
    "        self.middle = None\n",
    "        self.right = None\n",
    "    def __repr__(self):\n",
    "        return '2_3TreeNode({},{})'.format(self.key1, self.key2)\n",
    "    def is_leaf(self):\n",
    "        # 是否为叶子结点\n",
    "        return self.left is None and self.middle is None and self.right is None\n",
    "    def has_key2(self):\n",
    "        # 是否有key2\n",
    "        return self.key2 is not None\n",
    "    def has_key(self, key):\n",
    "        # 查找2-3树是否存在该值\n",
    "        if (self.key1 == key) or (self.key2 is not None and self.key2 == key):\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "    def get_child(self, key):\n",
    "        # 小于key1查找左边子树\n",
    "        if key < self.key1:\n",
    "            return self.left\n",
    "        elif self.key2 is None:\n",
    "            return self.middle # 没有key2就把中间子树作为右子树\n",
    "        elif key < self.key2:\n",
    "            return self.middle # 有key2，就和key2比较，比它小就是在中间子树\n",
    "        else:\n",
    "            return self.right # 比key2大，就往右子树\n",
    "\n",
    "class TwoThreeTree(object):\n",
    "    \"\"\"2-3查找树类\"\"\"\n",
    "    def __init__(self):\n",
    "        # 初始化，根结点为None\n",
    "        self.root=None\n",
    "    def is_empty(self): # 是否为空\n",
    "        return self.root is None\n",
    "    def get(self, key):\n",
    "        # 获取结点\n",
    "        if self.is_empty():\n",
    "            return None  # 如果是空，当然没有结果\n",
    "        else:\n",
    "            return self._get(self.root, key)\n",
    "    def _get(self, node, key):  # _表示私有函数概念\n",
    "        if self.is_empty():\n",
    "            return None\n",
    "        elif node.has_key(key): # None在逻辑判断中相当于False\n",
    "            # 如果有返回结果，则停止寻找，返回结果\n",
    "            return node\n",
    "        else:\n",
    "            child = node.get_child(key) # 若没有找到继续尝试寻找孩子结点\n",
    "            return self._get(child, key)\n",
    "    def search(self, key):\n",
    "        # 查找结点，有则返回True，没有则返回False\n",
    "        if self.get(key):\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "    def insert(self, key):\n",
    "        # 插入结点\n",
    "        if self.is_empty(): # 如果是空，直接赋值给根结点\n",
    "            self.root = Node(key)\n",
    "        else:\n",
    "            # 否则根据之前我们分析情况去进行插入，p_key和p_ref可以表示为临时保存\n",
    "            p_key, p_ref = self._insert(self.root, key)\n",
    "            if p_key is not None:\n",
    "                # 这里是最上层了，如果还有新插入的元素，\n",
    "                # 则需要把中间元素升为根结点\n",
    "                # 然后把剩下的两个元素拆分两边放在左子树(left)和中间子树(middle)\n",
    "                new_node = Node(p_key) # 这是提升的元素\n",
    "                new_node.left = self.root\n",
    "                new_node.middle = p_ref\n",
    "                self.root = new_node   # 变成根结点\n",
    "    def _insert(self, node, key):\n",
    "        if node.has_key(key): # 已经存在结点则无需再插入\n",
    "            return None, None\n",
    "        elif node.is_leaf(): # 如果是叶子结点,可以尝试插入\n",
    "            return self._add_to_node(node,key, None)\n",
    "        else:\n",
    "            # 不是叶子结点继续寻找孩子结点\n",
    "            child = node.get_child(key) # 比较插入值大小，判断往哪个子树寻找位置\n",
    "            p_key, p_ref = self._insert(child, key) # 递归尝试插入\n",
    "            if p_key is None: # 没有新插入元素，则无需处理\n",
    "                return None,None\n",
    "            else:\n",
    "                # 否则就需要尝试插入到该结点\n",
    "                return self._add_to_node(node, p_key, p_ref)\n",
    "    def _add_to_node(self, node, key, p_ref):\n",
    "        if node.has_key2(): # 如果已经有两个key，需要插入新元素后拆分剩余的元素\n",
    "            return self._split_node(node, key, p_ref)\n",
    "        else:\n",
    "            # 第一种情况，只有一个key的结点\n",
    "            if key < node.key1:   # 如果新元素比key1大，则代替key1,key1变为key2\n",
    "                node.key2 = node.key1\n",
    "                node.key1 = key\n",
    "                if p_ref is not None: # 如果有新孩子结点\n",
    "                    node.right = node.middle # 原来在中间子树移动到右子树\n",
    "                    node.middle = p_ref # 中间子树指向新孩子结点\n",
    "            else:\n",
    "                node.key2 = key  # 否则新元素为key2\n",
    "                if p_ref is not None: # 新孩子结点放在最右边\n",
    "                    node.right = p_ref\n",
    "            return None,None\n",
    "    def _split_node(self, node, key, p_ref):\n",
    "        # 当结点有3元素的时候，我们需要提升中间元素为父结点，拆分剩下的两个元素\n",
    "        # 左边元素原用之前的结点，右边元素用新结点\n",
    "        new_node = Node(None) # 新结点是给右边元素\n",
    "        if key < node.key1: # 如果新元素比key1小，那么就提升key1\n",
    "            p_key = node.key1         # key1为提升元素\n",
    "            node.key1 = key           # 新插入元素原用key1结点\n",
    "            new_node.key1 = node.key2 # key2是右边新元素\n",
    "            if p_ref is not None: # 如果新孩子结点\n",
    "                new_node.left = node.middle # 原结点的中间子树成为新结点左子树\n",
    "                new_node.middle = node.right # 原结点的右子树成为新结点中间子树\n",
    "                node.middle = p_ref # 把中间子树指向新孩子结点\n",
    "        # 如果新元素大于key1，小于key2，那么就提升新插入元素key\n",
    "        elif key < node.key2:\n",
    "            p_key = key               # key为提升元素\n",
    "            new_node.key1 = node.key2 # key2是右边新元素\n",
    "            if p_ref is not None:\n",
    "                new_node.left = p_ref # 把左子树指向新孩子结点\n",
    "                new_node.middle = node.right\n",
    "        else:\n",
    "            # 如果新插入元素大于key2，那么就提升key2\n",
    "            p_key = node.key2    # key2为提升元素\n",
    "            new_node.key1 = key  # key1是右边新结点\n",
    "            if p_ref is not None:\n",
    "                new_node.left = node.right # 原结点的右子树成为新结点左子树\n",
    "                new_node.middle = p_ref    # 新孩子结点成为新结点中间子树\n",
    "        node.key2 = None        # 提升后，原结点成为了2结点\n",
    "        return p_key, new_node  # 返回提升元素和新的孩子结点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = TwoThreeTree()\n",
    "for i in [5,9,1,3,6,10]:\n",
    "    t.insert(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = TwoThreeTree()\n",
    "for i in [5,9,1,3,6,10]:\n",
    "    t.insert(i)\n",
    "print(\"根结点：\", t.root)\n",
    "print(\"根结点左子树：\", t.root.left)\n",
    "print(\"根结点中间子树：\", t.root.middle)\n",
    "print(\"根结点右子树：\", t.root.right)\n",
    "t.insert(2)  # 插入新元素2\n",
    "print(\"当前根结点：\",t.root)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 红黑树\n",
    "\n",
    "[算法流程图](https://www.processon.com/view/link/5e01c9e8e4b0125e291952ad)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node():\n",
    "    \"\"\"定义红黑树结点类\"\"\"\n",
    "    def __init__(self, data):\n",
    "        self.data = data  # 元素值\n",
    "        self.parent = None  # 父亲结点\n",
    "        self.left = None  # 左子结点\n",
    "        self.right = None  # 右子结点\n",
    "        self.color = 1  # 颜色 1是红色, 0是黑色(在判断语句中0可以作为假)\n",
    "    def __repr__(self):\n",
    "        from pprint import pformat # 格式化打印\n",
    "        if self.left is None and self.right is None:  # 如果没有孩子结点就输出本结点元素值和颜色\n",
    "            return \"'%s %s'\" % (self.data, (self.color and \"红色\") or \"黑色\")\n",
    "        # 有孩子结点，先输出本结点元素值和颜色，再用()包含孩子结点的输出\n",
    "        return pformat(\n",
    "            {\n",
    "                \"%s %s\"\n",
    "                % (self.data, (self.color and \"红色\") or \"黑色\"): (self.left, self.right)\n",
    "            },\n",
    "            indent=1,\n",
    "        )\n",
    "class RedBlackTree():\n",
    "    \"\"\"红黑树类\"\"\"\n",
    "    def __init__(self):\n",
    "        # 定义叶子结点NONE\n",
    "        self.NONE = Node(None)\n",
    "        self.NONE.color = 0 # 根据定义，叶子结点一定是黑色\n",
    "        self.root = self.NONE\n",
    "\n",
    "    def __search_help(self, node, key):\n",
    "        if node == self.NONE or key == node.data:\n",
    "            return node\n",
    "        if key < node.data:\n",
    "            return self.__search_help(node.left, key)\n",
    "        return self.__search_help(node.right, key)\n",
    "    \n",
    "    def search(self, k):\n",
    "        \"\"\"寻找元素\"\"\"\n",
    "        return self.__search_help(self.root, k)\n",
    "    \n",
    "    def __fix_insert(self, k):\n",
    "        \"\"\"插入新元素后的调整\"\"\"\n",
    "        while k.parent.color == 1: # 第三种情况插入结点的父结点是红色\n",
    "            if k.parent == k.parent.parent.right: # 父结点是祖父结点的右结点\n",
    "                uncle = k.parent.parent.left  # 获取叔叔结点\n",
    "                if uncle.color == 1:\n",
    "                    # 案例1，父结点和叔叔结点为红色\n",
    "                    uncle.color = 0     # 叔叔结点变为黑色\n",
    "                    k.parent.color = 0  # 父结点变为黑色\n",
    "                    k.parent.parent.color = 1 # 祖父结点变为红色\n",
    "                    k = k.parent.parent  # 插入结点变为祖父结点\n",
    "                else:\n",
    "                    if k == k.parent.left:\n",
    "                        # 案例3：插入结点的父结点是祖父结点的右子结点，并且插入结点是其父结点的左子结点\n",
    "                        k = k.parent # 插入结点改为父结点\n",
    "                        self.right_rotate(k) # 右旋\n",
    "                    # 案例2：插入结点的父结点是祖父结点的右子结点，并且插入结点是其父结点的右子结点\n",
    "                    k.parent.color = 0 # 父结点变为黑色\n",
    "                    k.parent.parent.color = 1 # 祖父结点为红色\n",
    "                    self.left_rotate(k.parent.parent) # 左旋祖父结点\n",
    "            else:\n",
    "                uncle = k.parent.parent.right  # 获取叔叔结点\n",
    "\n",
    "                if uncle.color == 1:\n",
    "                    # 与案例1一样\n",
    "                    uncle.color = 0\n",
    "                    k.parent.color = 0\n",
    "                    k.parent.parent.color = 1\n",
    "                    k = k.parent.parent\n",
    "                else:\n",
    "                    if k == k.parent.right:\n",
    "                        # 案例3 镜像处理\n",
    "                        k = k.parent\n",
    "                        self.left_rotate(k)\n",
    "                    # 案例2 镜像处理\n",
    "                    k.parent.color = 0\n",
    "                    k.parent.parent.color = 1\n",
    "                    self.right_rotate(k.parent.parent)\n",
    "            if k == self.root: # 插入结点是根结点就不需要继续处理了\n",
    "                break\n",
    "        self.root.color = 0 # 最后确保根结点是黑色\n",
    "    def left_rotate(self, x):\n",
    "        \"\"\"左旋\"\"\"\n",
    "        y = x.right\n",
    "        x.right = y.left\n",
    "        if y.left != self.NONE:\n",
    "            y.left.parent = x\n",
    "\n",
    "        y.parent = x.parent\n",
    "        if x.parent == None:\n",
    "            self.root = y\n",
    "        elif x == x.parent.left:\n",
    "            x.parent.left = y\n",
    "        else:\n",
    "            x.parent.right = y\n",
    "        y.left = x\n",
    "        x.parent = y\n",
    "    def right_rotate(self, x):\n",
    "        \"\"\"右旋\"\"\"\n",
    "        y = x.left\n",
    "        x.left = y.right\n",
    "        if y.right != self.NONE:\n",
    "            y.right.parent = x\n",
    "\n",
    "        y.parent = x.parent\n",
    "        if x.parent == None:\n",
    "            self.root = y\n",
    "        elif x == x.parent.right:\n",
    "            x.parent.right = y\n",
    "        else:\n",
    "            x.parent.left = y\n",
    "        y.right = x\n",
    "        x.parent = y\n",
    "    def insert(self, key):\n",
    "        \"\"\"插入新元素，先插入到合适的位置，算法如二叉查找树插入，然后再调整结点，实现平衡\"\"\"\n",
    "        node = Node(key)  # 定义新元素结点\n",
    "        node.parent = None\n",
    "        node.data = key\n",
    "        node.left = self.NONE\n",
    "        node.right = self.NONE\n",
    "        node.color = 1  # 新结点一定是红色\n",
    "        y = None\n",
    "        x = self.root\n",
    "        while x != self.NONE:\n",
    "            y = x # 记录x当前结点\n",
    "            if node.data < x.data:\n",
    "                x = x.left\n",
    "            else:\n",
    "                x = x.right\n",
    "        # 找到合适的空位置\n",
    "        node.parent = y # y结点就是x的上一个结点，也就是父结点\n",
    "        if y == None:\n",
    "            self.root = node #如果是根结点，直接赋值\n",
    "        elif node.data < y.data:\n",
    "            # 比父结点小，在左子结点\n",
    "            y.left = node\n",
    "        else:\n",
    "            # 比父结点小，在右子结点\n",
    "            y.right = node\n",
    "        if node.parent == None:  # 如果父结点是空，说明它是根结点，根据定义，把颜色改为黑色便可\n",
    "            node.color = 0\n",
    "            return\n",
    "        if node.parent.parent == None: \n",
    "            # 如果祖父结点是空，那说明是根结点的子结点，根据定义父结点是黑色，可以直接插入，不处理\n",
    "            return\n",
    "        self.__fix_insert(node) #其他情况都需要调整结点\n",
    "    def get_root(self):\n",
    "        return self.root #返回根结点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rbt = RedBlackTree()\n",
    "rbt.insert(40)\n",
    "rbt.insert(32)\n",
    "rbt.insert(75)\n",
    "rbt.insert(50)\n",
    "rbt.insert(90)\n",
    "print(\"插入新元素前:\",  rbt.get_root())\n",
    "rbt.insert(98)\n",
    "print(\"插入新元素后：\", rbt.get_root())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 挑战：二叉树园丁"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from tools import TreeNode as Node, print_tree  # 引用tools.py上的结点类和函数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insert_node(root, arr, i):\n",
    "    \"\"\"根据题目要求，用列表构建二叉树\"\"\"\n",
    "    if i < len(arr): # 如果没有超出列表范围，开始插入新结点\n",
    "        if arr[i] is None: # 如果是空结点，返回None作为空结点\n",
    "            return None\n",
    "        else:\n",
    "            root = Node(arr[i]) # 有值，这创建新的结点\n",
    "            root.left = insert_node(root.left, arr, 2*i+1) # 然后尝试寻找它的左结点\n",
    "            root.right = insert_node(root.right, arr, 2*i+2) # 寻找它的右结点\n",
    "            return root  # 返回新结点\n",
    "    return root\n",
    "def cut_tree(root):\n",
    "    \"\"\"裁剪二叉树，把不含有【1】的分支都删掉\"\"\"\n",
    "    def sum_value(node):\n",
    "        \"\"\"求树的总和，包括其自身元素值和它的左右子树的元素值总和\"\"\"\n",
    "        if not node:    # 如果是空叶子也返回0\n",
    "            return 0\n",
    "        total_left = sum_value(node.left)   # 递归计算左子树的元素值总和\n",
    "        total_right = sum_value(node.right) # 递归计算右子树的元素值总和\n",
    "        if total_left == 0:   # 如果总和为0,则说明该子树没有包含【1】\n",
    "            node.left = None\n",
    "        if total_right == 0:\n",
    "            node.right = None\n",
    "        # 返回该结点包含的元素\n",
    "        return total_left + total_right + node.value\n",
    "    if sum_value(root) > 0: # 如果根结点元素总和大于0\n",
    "        return root         # 返回根结点\n",
    "    return None             # 否则返回空，整棵树删掉"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "arr = [1,0,1,0,None,0,0,0,0,1]\n",
    "root = insert_node(None,arr,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print_tree(root)\n",
    "cut_tree(root)\n",
    "print_tree(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Python中内置查找函数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "citys = [\"广州\", \"北京\", \"深圳\", \"上海\", \"肇庆\"]\n",
    "# 深圳是否在列表中？\n",
    "print(\"深圳\" in citys)\n",
    "print(\"武汉\" in citys)\n",
    "print(\"上海的位置：\", citys.index(\"上海\"))\n",
    "print(\"北京有几个：\", citys.count(\"北京\"))\n",
    "citys.insert(1,\"佛山\")\n",
    "citys"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "name = \"Louis David\"\n",
    "\"D\" in name\n",
    "\"c\" in name\n",
    "name.index('s')\n",
    "name.count('i')\n",
    "name.find('i')\n",
    "name.find('i', 4)\n",
    "name.find('David')\n",
    "name.find('i', 1, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = \"string to list\" # list()函数把字符串变为列表\n",
    "a = list(a) # ['s', 't', 'r', 'i', 'n', 'g', ' ', 't', 'o', ' ', 'l', 'i', 's', 't']\n",
    "a.insert(10,\"new \") # 插入新元素\n",
    "print(\"\".join(a)) # 列表变为字符串"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## 哈希查找--字典类型\n",
    "data = {\n",
    "    \"20190106\":{\"name\":\"小明\", \"score\":90},\n",
    "    \"20190107\":{\"name\":\"小闲\", \"score\":70},\n",
    "    \"20190108\":{\"name\":\"小丘\", \"score\":80},\n",
    "    \"20190108\":{\"name\":\"小可\", \"score\":85},\n",
    "}\n",
    "data['20190106']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 挑战：不可攻破的密码"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint, sample  # 随机函数\n",
    "import string # 字符类"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "special_characters = list(string.punctuation) # 特殊字符列表\n",
    "def strong_password(password):\n",
    "    password = list(password) # 把字符串转化为列表，因为字符串插入元素不好处理\n",
    "    # 先看是否有三种类型的字符\n",
    "    has_uppercase = False # 是否有大写字母\n",
    "    has_lowercase = False # 是否有小写字母\n",
    "    has_digits = False       # 是否有数字\n",
    "    for letter in password:\n",
    "        if letter in string.ascii_uppercase: # 判断是否有大写字母\n",
    "            has_uppercase = True\n",
    "            continue\n",
    "        if letter in string.ascii_lowercase: # 判断是否有小写字母\n",
    "            has_lowercase = True\n",
    "            continue\n",
    "        if letter in string.digits: # 判断是否有数字\n",
    "            has_digits = True\n",
    "            continue\n",
    "        if has_uppercase and has_lowercase and has_digits:\n",
    "            break # 如果已经符合要求，就不需要继续查找\n",
    "    # 是否需要补充字符\n",
    "    if not has_uppercase:\n",
    "        position = randint(0, len(password)-1) # 生成随机位置\n",
    "        letter = string.ascii_uppercase[randint(0, 25)] # 生成随机大写字符\n",
    "        password.insert(position, letter) # 插入到密码当中\n",
    "    if not has_lowercase:\n",
    "        position = randint(0, len(password)-1)\n",
    "        letter = string.ascii_lowercase[randint(0, 25)]\n",
    "        password.insert(position, letter)\n",
    "    if not has_digits:\n",
    "        position = randint(0, len(password)-1)\n",
    "        letter = str(randint(0, 9))\n",
    "        password.insert(position, letter)\n",
    "    # 检查是否有连续相同字符\n",
    "    new_password = password.copy() # 新密码\n",
    "    same_letter_count = 1 # 统计字符连续出现次数\n",
    "    add_count = 0 # 插入新元素数量\n",
    "    for i in range(0, len(password)):\n",
    "        if i > 0:\n",
    "            if password[i] == password[i-1]: # 和前一个元素比较\n",
    "                same_letter_count += 1 # 若相同，记录加1\n",
    "            else:\n",
    "                same_letter_count = 1 # 若不同，回到数量1\n",
    "        if same_letter_count > 2: # 如果连续出现次数超过2次\n",
    "            letter = special_characters[randint(0, len(special_characters)-1)]\n",
    "            new_password.insert(i + add_count, letter) # 在该元素前插入新元素，截断连续\n",
    "            add_count += 1 # 为了调整插入位置偏移，记录添加新元素数量\n",
    "            same_letter_count = 1 # 截断连续字符后，回到数量1 \n",
    "    # 字符数量是否不少于8个\n",
    "    while len(new_password) < 8:\n",
    "        letters = sample(special_characters, 8-len(new_password)) # 一次随机抽样n个特殊字符\n",
    "        new_password += \"\".join(letters) # 若不够8个字符，补足\n",
    "    return \"\".join(new_password) # 输出结果转化为字符串"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(strong_password(\"test1\"))\n",
    "print(strong_password(\"123456\"))\n",
    "print(strong_password(\"111111\"))\n",
    "print(strong_password(\"password\"))\n",
    "print(strong_password(\"Aabc1234\"))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
